package com.leetcode.algorithm.y19.m11;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Calendar;
import java.util.List;

/**
 * 
 * (done)1184. 公交站间的距离
 * (done)1185. 一周中的第几天
 * (done)1200. 最小绝对差
 * (done)1217. 玩筹码
 * (done)1232. 缀点成线
 * 
 * @author jie.deng
 * @time 2019年11月29日 上午8:55:08
 */
public class MySolution1129 {
	
	/**
	 * (done)1184. 公交站间的距离
	 * 
     * 环形公交路线上有 n 个站，按次序从 0 到 n - 1 进行编号。我们已知每一对相邻公交站之间的距离，distance[i] 表示编号为 i 的车站和编号为 (i + 1) % n 的车站之间的距离。
     * 
     * 环线上的公交车都可以按顺时针和逆时针的方向行驶。
     * 
     * 返回乘客从出发点 start 到目的地 destination 之间的最短距离。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 
     * 
     * 输入：distance = [1,2,3,4], start = 0, destination = 1
     * 输出：1
     * 解释：公交站 0 和 1 之间的距离是 1 或 9，最小值是 1。
     *  
     * 
     * 示例 2：
     * 
     * 
     * 
     * 输入：distance = [1,2,3,4], start = 0, destination = 2
     * 输出：3
     * 解释：公交站 0 和 2 之间的距离是 3 或 7，最小值是 3。
     *  
     * 
     * 示例 3：
     * 
     * 
     * 
     * 输入：distance = [1,2,3,4], start = 0, destination = 3
     * 输出：4
     * 解释：公交站 0 和 3 之间的距离是 6 或 4，最小值是 4。
     *  
     * 
     * 提示：
     * 
     * 1 <= n <= 10^4
     * distance.length == n
     * 0 <= start, destination < n
     * 0 <= distance[i] <= 10^4
     * 
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/distance-between-bus-stops
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
	 * 
	 * @param distance
	 * @param start
	 * @param destination
	 * @return
	 */
	public int distanceBetweenBusStops(int[] distance, int start, int destination) {
		if (start == destination) {
			return 0;
		}
		int min = start, max = destination;
		if (start > destination) {
			min = destination;
			max = start;
		}
		// 计算[min,max)的距离
		int minDis = 0;
		int dis = 0;
		for (int i = min; i < max; i++) {
			dis += distance[i];
		}
		minDis = dis;
		// 计算[max-min) = [max,n)+[0,min)的距离
		dis = 0;
		for (int i = max; i < distance.length && dis < minDis; i++) {
			dis += distance[i];
		}
		if (dis < minDis) {
			for (int i = 0; i < min && dis < minDis; i++) {
				dis += distance[i];
			}
		}
		return Math.min(dis, minDis);
	}
    
    /**
     * (done)1185. 一周中的第几天
     * 
     * 给你一个日期，请你设计一个算法来判断它是对应一周中的哪一天。
     * 
     * 输入为三个整数：day、month 和 year，分别表示日、月、年。
     * 
     * 您返回的结果必须是这几个值中的一个 {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 输入：day = 31, month = 8, year = 2019
     * 输出："Saturday"
     * 示例 2：
     * 
     * 输入：day = 18, month = 7, year = 1999
     * 输出："Sunday"
     * 示例 3：
     * 
     * 输入：day = 15, month = 8, year = 1993
     * 输出："Sunday"
     *  
     * 
     * 提示：
     * 
     * 给出的日期一定是在 1971 到 2100 年之间的有效日期。
     * 
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/day-of-the-week
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 
     * 
     * @param day
     * @param month
     * @param year
     * @return
     */
	public String dayOfTheWeek(int day, int month, int year) {
		String[] days = new String[] { "", "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday",
				"Sunday" };
		Calendar cal = Calendar.getInstance();
		cal.set(year, month - 1, day);
		return days[cal.get(Calendar.DAY_OF_WEEK)];
	}	
	
    /**
     * (done)1200. 最小绝对差
     * 
     * 给你个整数数组 arr，其中每个元素都 不相同。
     * 
     * 请你找到所有具有最小绝对差的元素对，并且按升序的顺序返回。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 输入：arr = [4,2,1,3]
     * 输出：[[1,2],[2,3],[3,4]]
     * 示例 2：
     * 
     * 输入：arr = [1,3,6,10,15]
     * 输出：[[1,3]]
     * 示例 3：
     * 
     * 输入：arr = [3,8,-10,23,19,-4,-14,27]
     * 输出：[[-14,-10],[19,23],[23,27]]
     *  
     * 
     * 提示：
     * 
     * 2 <= arr.length <= 10^5
     * -10^6 <= arr[i] <= 10^6
     * 
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/minimum-absolute-difference
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * 
     * @param arr
     * @return
     */
	public List<List<Integer>> minimumAbsDifference(int[] arr) {
		Arrays.sort(arr);
		int[] dis = new int[arr.length - 1];
		for (int i = 0; i < arr.length - 1; i++) {
			dis[i] = arr[i + 1] - arr[i];
		}
		List<List<Integer>> retList = new ArrayList<List<Integer>>();
		int minDis = dis[0];
		for (int i = 0; i < dis.length; i++) {
			if (dis[i] < minDis) {
				minDis = dis[i];
			}
		}
		for (int i = 0; i < dis.length; i++) {
			if (dis[i] == minDis) {
				retList.add(Arrays.asList(arr[i], arr[i + 1]));
			}
		}
		return retList;
	}
    
    /**
     * (done)1217. 玩筹码
     *
     * 数轴上放置了一些筹码，每个筹码的位置存在数组 chips 当中。
     * 
     * 你可以对 任何筹码 执行下面两种操作之一（不限操作次数，0 次也可以）：
     * 
     * 将第 i 个筹码向左或者右移动 2 个单位，代价为 0。
     * 将第 i 个筹码向左或者右移动 1 个单位，代价为 1。
     * 最开始的时候，同一位置上也可能放着两个或者更多的筹码。
     * 
     * 返回将所有筹码移动到同一位置（任意位置）上所需要的最小代价。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 输入：chips = [1,2,3]
     * 输出：1
     * 解释：第二个筹码移动到位置三的代价是 1，第一个筹码移动到位置三的代价是 0，总代价为 1。
     * 示例 2：
     * 
     * 输入：chips = [2,2,2,3,3]
     * 输出：2
     * 解释：第四和第五个筹码移动到位置二的代价都是 1，所以最小总代价为 2。
     *  
     * 
     * 提示：
     * 
     * 1 <= chips.length <= 100
     * 1 <= chips[i] <= 10^9
     * 
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/play-with-chips
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * 
     * @param chips
     * @return
     */
	public int minCostToMoveChips(int[] chips) {
		int cntOfEven = 0;
		for (int i = 0; i < chips.length; i++) {
			if (chips[i] % 2 == 0) {
				cntOfEven++;
			}
		}
		return Math.min(cntOfEven, chips.length - cntOfEven);
	}
    
    /**
     * (done)1232. 缀点成线
     * 
     * 在一个 XY 坐标系中有一些点，我们用数组 coordinates 来分别记录它们的坐标，其中 coordinates[i] = [x, y] 表示横坐标为 x、纵坐标为 y 的点。
     * 
     * 请你来判断，这些点是否在该坐标系中属于同一条直线上，是则返回 true，否则请返回 false。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 
     * 
     * 输入：coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]
     * 输出：true
     * 示例 2：
     * 
     * 
     * 
     * 输入：coordinates = [[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]]
     * 输出：false
     *  
     * 
     * 提示：
     * 
     * 2 <= coordinates.length <= 1000
     * coordinates[i].length == 2
     * -10^4 <= coordinates[i][0], coordinates[i][1] <= 10^4
     * coordinates 中不含重复的点
     * 
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/check-if-it-is-a-straight-line
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * 
     * @param coordinates
     * @return
     */
	public boolean checkStraightLine(int[][] coordinates) {
		for (int i = 3; i < coordinates.length; i++) {
			if ((coordinates[i][1] - coordinates[0][1])
					* (coordinates[i][0] - coordinates[1][0]) != (coordinates[i][0] - coordinates[0][0])
							* (coordinates[i][1] - coordinates[1][1])) {
				return false;
			}
		}
		return true;
	}
}
